package Link;

public class leet_21 {
    public static void main(String[] args) {
        ListNode dzb2 = new ListNode(2);


        ListNode l1 = new ListNode(1);

        Solution_21 p =new Solution_21();
        ListNode result = p.mergeTwoLists(dzb2, l1);
        while(result!=null){
            System.out.println(result.val);
            result = result.next;
        }

    }
}

class Solution_21 {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode result = concatMerge(l1, l2);
        return result;
    }

    /**
     * 递归算法
     * @param l1
     * @param l2
     * @return
     */
    public ListNode dieMerge(ListNode l1, ListNode l2){
        if(l1==null){
            return l2;
        }
        if(l2==null){
            return l1;
        }
        if(l1.val > l2.val){
            l2.next = dieMerge(l1, l2.next);
            return l2;
        }else{
            l1.next = dieMerge(l1.next, l2.next);
            return l1;
        }
    }


    /**
     * 迭代算法
     * @param l1
     * @param l2
     * @return
     */
    public ListNode concatMerge(ListNode l1, ListNode l2){
        if(l1==null){
            return l2;
        }
        if(l2==null){
            return l1;
        }

        ListNode currA = l1;
        ListNode currB = l2;
        // 构建的合并结点
        ListNode prev = new ListNode();
        // 首先确认头结点是谁 如果相同优先让A链表为主
        if(currA.val > currB.val){
            prev = currB;
            currB = currB.next;
        }else{
            prev = currA;
            currA = currA.next;
        }
        // 返回的结点的首节点
        ListNode result = prev;

        while(currA!=null || currB!=null){
            if(currA==null){
                // 此时让prev指向下一个节点
                // 并把currB 变为下一个节点
                prev.next = currB;
                break;
            }else if(currB==null){
                // 此时让prev指向下一个节点
                // 并把currA 变为下一个节点
                prev.next = currA;
                break;
            }else if(currA.val > currB.val){
                prev.next=currB;
                prev = prev.next;
                currB=currB.next;
            }else if(currA.val <= currB.val){
                prev.next = currA;
                prev=prev.next;
                currA=currA.next;
            }
        }
        return result;
    }
}

